signature CFG_STRUCTS =
sig
  include ATOMS
  structure Types : TYPES2
end

signature CFG =
sig
  include CFG_STRUCTS

  structure Binop :
  sig
    datatype t
      = Plus
      | Minus
      | Times
      | Divide
      | Modus
      | Not
      | And
      | Or
      | Eq
      | Ne
      | Gt
      | Ge
      | Lt
      | Le

    val equals : t * t -> bool
    val toString : t -> string
  end
  
  structure Operand :
  sig
    datatype t
      = OpVoid
      | IntNum of Intl.t
      | Var of {id : Id.t, ty : Types.t}
      | True
      | False
      | Null
      | Mem of {id : Id.t, ty : Types.t}
    
    val dest : t -> Id.t option
    val equals : t * t -> bool
    val getConst : t -> t option
    val getOneConst : t list -> t
    val getOneVar : t list -> t
    val getVar : t -> t option
    val isConst : t -> bool
    val isConsts : t list -> bool
    val isConstsAndEqual : t list -> bool
    val isVar : t -> bool
    val isMem : t -> bool
    val isZero : t -> bool
    val orig : t -> Id.t list
    val substConst : t * Id.t * t -> t
    val substId : t * (Id.t -> Id.t) -> t  
    val toString : t -> string
  end

  structure Stm :
  sig
    datatype t
      = Assign of {line : Counter.t, dest : Operand.t, src : Operand.t, ty : Types.t}
      | AssignExp of {line : Counter.t, dest : Operand.t, bop : Binop.t, src : Operand.t list, ty : Types.t}
      | AssignCall of {line : Counter.t, fid : Id.t, dest : Operand.t, src : Operand.t list}
      | Call of {line : Counter.t, fid : Id.t, src : Operand.t list}
      | Exp of {line : Counter.t, src : Operand.t}
      | Alloc of {line : Counter.t, ty : Types.t, dest : Operand.t}
      | Free of {line : Counter.t, ty : Types.t, src : Operand.t}
      | Label of {id : Id.t}
      | Phi of {line : Counter.t, dest : Operand.t, src : {operand : Operand.t, from : Id.t} list}
      | SJump of {line : Counter.t, label : Id.t}
      | SIf of {line : Counter.t, value : Operand.t, truee : Id.t, falsee : Id.t}
  
    val bogus : unit -> t
    val cookDest : t -> Id.t option
    val equals : t * t -> bool
    val equalsStms : t list * t list -> bool
    val getPhiOperand : {operand : Operand.t, from : Id.t} list -> Operand.t list
    val getPhiSrc : t -> Operand.t list
    val getLine : t -> Counter.t
    val isAssignMem : t -> bool
    val isPhi : t -> bool
    val substConst : t * Id.t * Operand.t -> t
    val substDest : t * (Id.t -> Id.t) -> t
    val substPhi : t * (Id.t -> Id.t) * Id.t -> t
    val substCopyPropUses : t * (Id.t -> Id.t) -> t
    val substUses : t * (Id.t -> Id.t) -> t
    val toString : t -> string
    val uses : t -> Id.t list
    val usesId : t * Id.t -> bool
    val withSideEffects : t -> bool
  end
  
  structure Transfer :
  sig
    datatype t
      = Jump of {line : Counter.t, label : Id.t}
      | If of {line : Counter.t, value : Operand.t, truee : Id.t, falsee : Id.t}
      | Return of {line : Counter.t, value : Operand.t}
    
    val bogus : unit -> t
    val getLine : t -> Counter.t
    val substUses : t * (Id.t -> Id.t) -> t
    val substConst : t * Id.t * Operand.t -> t
    val toString : t -> string
    val uses : t -> Id.t list
    val usesId : t * Id.t -> bool
  end
  
  structure Block :
  sig
    datatype t
      = T of {name : Id.t,
              prop : bool,
              stms : Stm.t list,
              transfer : Transfer.t,
              successors : Id.t list}
    
    val addStm : t * Stm.t -> t
    val addStmEnd : t * Stm.t -> t
    val addStmsEnd : t * Stm.t list -> t
    val equals : t * t -> bool
    val getAllPhi : t -> Stm.t list
    val name : t -> Id.t
    val orig : t -> Id.t list
    val stms : t -> Stm.t list
    val successors : t -> Id.t list
    val toString : t -> string
    val toStringDot : t -> string
  end

  structure Structs :
  sig
    datatype t
      = T of {name : Id.t,
              fields : {id : Id.t, ty : Types.t} list}
              
    val bogus : unit -> t
    val equals : t * t -> bool
    val toString : t -> string
  end

  structure Function :
  sig
    datatype t
      = T of {name : Id.t,
              exit : Id.t,
              rettype : Types.t,
              args : {id : Id.t, ty : Types.t} list,
              locals : {id : Id.t, ty : Types.t} list,
              blocks : Block.t list,
              pre : Operand.t,
              post : Operand.t}
              
    val addBlock : t * Block.t -> t
    val df : t -> {graph : unit DiGraph.t, getDf : unit DiGraph.Node.t -> unit DiGraph.Node.t list}
    val dfs : t -> unit
    val dfsTree : t -> Block.t Tree.t
    val dominatorTree : t -> {tree : Block.t Tree.t,
                              labelTreeNode : Id.t -> Id.t list}
    val fromGraph : unit DiGraph.t -> Block.t list
    val getAllPhi : t * Id.t -> Stm.t list
    val isEmptyBlock : t * Id.t -> Id.t option
    val name : t -> Id.t
    val reachable : t * Id.t -> Id.t list
    val ssaUtil : t -> {graph : unit DiGraph.t,
                        getBlock : unit DiGraph.Node.t -> Block.t option,
                        setBlock : unit DiGraph.Node.t * Block.t option -> unit,
                        getDf : unit DiGraph.Node.t -> unit DiGraph.Node.t list,
                        labelNode : Id.t -> unit DiGraph.Node.t,
                        getName : unit DiGraph.Node.t -> Id.t}
    val setNameGraph : t -> {graph : unit DiGraph.t,
                             getName : unit DiGraph.Node.t -> Id.t,
                             labelNode : Id.t -> unit DiGraph.Node.t}
    val stringName : t -> string
    val toGraph : t -> unit DiGraph.t
    val toReverseGraph : t -> {graph : Id.t DiGraph.t, getName : Id.t DiGraph.Node.t -> Id.t}
    val toDot : t * string -> unit
    val reverseGraphToDot : t * string -> unit
    val toDotDomTree : t -> unit
    val toDotTree : t -> unit
    val toString : t -> string
  end

  structure Program :
  sig
    datatype t
      = T of {structs : Structs.t list,
              gvars : {id : Id.t, ty : Types.t} list,
              funcs : Function.t list}

    val bogus : unit -> t
    val reverseToDot : t * string -> unit
    val toDot : t * string -> unit
    val toString : t -> string
  end
  
  
end
